﻿#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 6  
#define INF 99999    


typedef struct Node {
    int vertex;
    struct Node* next;
} Node;


typedef struct Graph {
    Node* head[MAX_NODES];
} Graph;

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void initGraph(Graph* graph) {
    for (int i = 0; i < MAX_NODES; i++) {
        graph->head[i] = NULL;
    }
}


void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->head[src];
    graph->head[src] = newNode;
}

void dfs(Graph* graph, int start, int end, int visited[], int path[], int pathLength) {
    visited[start] = 1;
    path[pathLength] = start;
    pathLength++;

    if (start == end) {

        for (int i = 0; i < pathLength; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    else {

        Node* temp = graph->head[start];
        while (temp) {
            if (!visited[temp->vertex]) {
                dfs(graph, temp->vertex, end, visited, path, pathLength);
            }
            temp = temp->next;
        }
    }


    visited[start] = 0;
}


void dfsLength3(Graph* graph, int start, int end, int visited[], int path[], int pathLength) {
    if (pathLength > 3) return;

    visited[start] = 1;
    path[pathLength] = start;
    pathLength++;

    if (start == end && pathLength == 4) {
        for (int i = 0; i < pathLength; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    else {
        Node* temp = graph->head[start];
        while (temp) {
            if (!visited[temp->vertex]) {
                dfsLength3(graph, temp->vertex, end, visited, path, pathLength);
            }
            temp = temp->next;
        }
    }

    visited[start] = 0;
}

void bfsShortestPath(Graph* graph, int start, int end) {
    int queue[MAX_NODES], front = 0, rear = 0;
    int distance[MAX_NODES], parent[MAX_NODES];
    int visited[MAX_NODES] = { 0 };

    for (int i = 0; i < MAX_NODES; i++) {
        distance[i] = INF;
        parent[i] = -1;
    }


    queue[rear++] = start;
    visited[start] = 1;
    distance[start] = 0;


    while (front != rear) {
        int current = queue[front++];
        Node* temp = graph->head[current];

        while (temp) {
            int neighbor = temp->vertex;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                distance[neighbor] = distance[current] + 1;
                parent[neighbor] = current;
                queue[rear++] = neighbor;

                if (neighbor == end) {

                    int path[MAX_NODES], pathLength = 0;
                    for (int v = end; v != -1; v = parent[v]) {
                        path[pathLength++] = v;
                    }
                    printf("最短路径: ");
                    for (int i = pathLength - 1; i >= 0; i--) {
                        printf("%d ", path[i]);
                    }
                    printf("\n");
                    return;
                }
            }
            temp = temp->next;
        }
    }
}


int main() {
    Graph graph;
    initGraph(&graph);


    addEdge(&graph, 5, 0);
    addEdge(&graph, 5, 1);
    addEdge(&graph, 5, 4);
    addEdge(&graph, 0, 1);
    addEdge(&graph, 1, 2);
    addEdge(&graph, 3, 2);
    addEdge(&graph, 4, 3);
    addEdge(&graph, 5, 3);
    addEdge(&graph, 3, 5);
    addEdge(&graph, 0, 3);
    addEdge(&graph, 2, 0);

    int visited[MAX_NODES] = { 0 };
    int path[MAX_NODES];

    printf("从顶点 5 到顶点 2 的所有简单路径:\n");
    dfs(&graph, 5, 2, visited, path, 0);

    printf("从顶点 5 到顶点 2 的所有长度为 3 的简单路径:\n");
    dfsLength3(&graph, 5, 2, visited, path, 0);

    printf("从顶点 5 到顶点 2 的最短路径:\n");
    bfsShortestPath(&graph, 5, 2);

    return 0;
}
